The TRIANGULATE procedure constructs a Delaunay triangulation of a planar set of points. Delaunay triangulations are very useful for the interpolation, analysis, and visual display of irregularly-gridded data. In most applications, after the irregularly gridded data points have been triangulated, the function TRIGRID is invoked to interpolate surface values to a regular grid. TRIANGULATE uses double precision for all computations.
Since Delaunay triangulations have the property that the circumcircle of any triangle in the triangulation contains no other vertices in its interior, interpolated values are only computed from nearby points.
TRIANGULATE can, optionally, return the adjacency list that describes, for each node, the adjacent nodes in the Delaunay triangulation. With this list, the Voronoi polygon (the polygon described by the set of points which are closer to that node than to any other node) can be computed for each node. This polygon contains the area influenced by its associated node. Tiling of the region in this manner is also called Dirichlet, Wigner-Seithz, or Thiessen tessellation.
The grid returned by the TRIGRID function can be input to various routines such as SURFACE, TV, and CONTOUR. See the description of TRIGRID for an example.
TRIANGULATE and TRIGRID can also be used to perform gridding and interpolation over the surface of a sphere. The interpolation is C1 continuous, meaning that the result is continuous over both the function value and its first derivative. This feature is ideal for interpolating an irregularly-sampled dataset over part or all of the surface of the earth (or other (spherical) celestial bodies). Extrapolation outside the convex hull of sample points is also supported. To perform spherical gridding, you must include the FVALUE and SPHERE keywords described below. The spherical gridding technique used in IDL is based on the paper “Interpolation of Data on the Surface of a Sphere”, R. Renka, Oak Ridge National Laboratory Report ORNL/CSD-108, 1982.
The TRIANGULATE procedure uses the divide-and-conquer method described in “Two Algorithms for Constructing a Delaunay Triangulation,” D.T. Lee and B.J. Schachter, Int. J. of Computer and Information Sci., Vol. 9, 1980, pp. 219-242.
TRIANGULATE, X, Y, Triangles [, B] [, CONNECTIVITY=variable] [, SPHERE=variable [, /DEGREES]] [, FVALUE=variable] [, REPEATS=variable] [, TOLERANCE=value]
An array that contains the X coordinates of the points to be triangulated.
An array that contains the Y coordinates of the points to be triangulated. Parameters X and Y must have the same number of elements.
A named variable that, on exit, contains the list of triangles in the Delaunay triangulation of the points specified by the X and Y arguments. Triangles is a longword array dimensioned (3, number of triangles), where Triangles[0, i], Triangles[1, i], and Triangles[2, i] contain the indices of the vertices of the i-th triangle (i.e., X[Tr[*, i]] and Y[Triangles[*, i]] are the X and Y coordinates of the vertices of the i-th triangle).
An optional, named variable that, upon return, contains a list of the indices of the boundary points in counterclockwise order.
Set this keyword to a named variable in which the adjacency list for each of the N nodes (xy point) is returned. The list has the following form:
Each element i, 0 ≤i < N, contains the starting index of the connectivity list for node i within the list array. To obtain the adjacency list for node i, extract the list elements from LIST[i] to LIST[i+1]-1.
The adjacency list is ordered in the counter-clockwise direction. The first item on the list of boundary nodes is the subscript of the node itself. For interior nodes, the list contains the subscripts of the adjacent nodes in counter-clockwise order.
For example, the call:
TRIANGULATE, X, Y, CONNECTIVITY = LIST
returns the adjacency list in the variable LIST.
The subscripts of the nodes adjacent to X[i] and Y[i] are contained in the array:
LIST[LIST[i] : LIST[i+1]-1]
Set this keyword to indicate that the X and Y arguments contain longitude and latitude coordinates specified in degrees. This keyword is only effective if the SPHERE keyword is specified. If DEGREES is not set, X and Y are assumed to be specified in radians when a spherical triangulation is performed.
Set this keyword to a named variable that contains sample values for each longitude/latitude point in a spherical triangulation. On output, the elements of FVALUE are rearranged to correspond to the new ordering of X and Y (as described in the SPHERE keyword, below). This reordered array can be passed to TRIGRID to complete the interpolation.
Set this keyword to a named variable to return a (2, n) list of the indices of duplicated points. That is, for each i,
X[REPEATS[0,i]] = X[REPEATS[1,i]]
and
Y[REPEATS[0,i]] = Y[REPEATS[1,i]]
Note: Use the GRID_INPUT procedure to handle repeated points (duplicate locations).
Set this keyword to a named variable in which the results from a spherical triangulation are returned. This result is a structure that can be passed to TRIGRID to perform spherical gridding. The structure contains the 3D Cartesian locations sample points and the adjacency list that describes the triangulation.
When spherical triangulation is performed, X and Y are interpreted as longitude and latitude, in either degrees or radians (see the DEGREES keyword, above). The X and Y parameters are converted to double precision and are rearranged to match the spherical triangulation.
Set this keyword to the tolerance to be used when determining whether points are colinear. If X and Y are double-precision values, the default is 10-12 * Max(X,Y); otherwise the default is 10-6 * Max(X,Y), where Max(X,Y) is the maximum absolute value of the X and Y arrays. If three points are colinear within the given tolerance, a triangle will not be constructed for those points. The default is zero, which assumes that none of the points are colinear.
Tip: TRIANGULATE is typically used for irregular grids, where none of the points are colinear. For regular or semi-regular grids, you can use the TOLERANCE value to avoid creating artificial triangles along the boundary, and to triangulate the appropriate points within the grid. In this case, an appropriate tolerance value might be 10-6 * Max(X,Y), where Max(X,Y) is the maximum absolute value of the X and Y arrays.
For some examples using the TRIANGULATE routine, see the TRIGRID function.
|
Pre-4.0 |
Introduced |